//给你一个 从 0 开始的排列 nums（下标也从 0 开始）。请你构建一个 同样长度 的数组 ans ，其中，对于每个 i（0 <= i < nums.
//length），都满足 ans[i] = nums[nums[i]] 。返回构建好的数组 ans 。 
//
// 从 0 开始的排列 nums 是一个由 0 到 nums.length - 1（0 和 nums.length - 1 也包含在内）的不同整数组成的数组。
// 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [0,2,1,5,3,4]
//输出：[0,1,2,4,5,3]
//解释：数组 ans 构建如下：
//ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4
//]], nums[nums[5]]]
//    = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
//    = [0,1,2,4,5,3] 
//
// 示例 2： 
//
// 
//输入：nums = [5,0,1,2,3,4]
//输出：[4,5,0,1,2,3]
//解释：数组 ans 构建如下：
//ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4
//]], nums[nums[5]]]
//    = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]
//    = [4,5,0,1,2,3] 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 1000 
// 0 <= nums[i] < nums.length 
// nums 中的元素 互不相同 
// 
//
// 
//
// 进阶：你能在不使用额外空间的情况下解决此问题吗（即 O(1) 内存）？ 
//
// Related Topics 数组 模拟 👍 86 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-05-06 09:30:13
 * @description 1920.基于排列构建数组
 
 */
 
public class BuildArrayFromPermutation {
    public static void main(String[] args) {
    //测试代码
    BuildArrayFromPermutation fun = new BuildArrayFromPermutation();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] buildArray1(int[] nums) {
        int len = nums.length;
        int [] res=new int[len];
        for (int i = 0; i < nums.length; i++) {
            res[i]=nums[nums[i]];
        }
        return res;
    }

    /*
我们也可以直接对原数组 nums 进行修改。
为了使得构建过程可以完整进行，我们需要让 nums 中的每个元素 nums[i] 能够同时存储「当前值」（即 nums[i]）和「最终值」（即 nums[nums[i]]）。
我们注意到 nums 中元素的取值范围为 [0,999] 闭区间，这意味着 nums 中的每个元素的「当前值」和「最终值」都在 [0,999] 闭区间内。
因此，我们可以使用类似「1000 进制」的思路来表示每个元素的「当前值」和「最终值」。对于每个元素，我们用它除以 1000 的商数表示它的「最终值」，而用余数表示它的「当前值」。
那么，我们首先遍历 nums，计算每个元素的「最终值」，并乘以 1000 加在该元素上。随后，我们再次遍历数组，并将每个元素的值除以 1000 保留其商数。此时 nums 即为构建完成的数组，我们返回该数组作为答案。
在计算 nums[i] 的「最终值」并修改该元素时，我们需要计算修改前 nums[nums[i]] 的值，而 nums 中下标为 nums[i] 的元素可能已被修改，因此我们需要将取下标得到的值对 1000 取模得到「最终值」

    * */
    public int[] buildArray(int[] nums) {
        int n = nums.length;
        // 第一次遍历编码最终值
        for (int i = 0; i < n; ++i) {
            nums[i] += 1000 * (nums[nums[i]] % 1000);
        }
        // 第二次遍历修改为最终值
        for (int i = 0; i < n; ++i) {
            nums[i] /= 1000;
        }
        return nums;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
